#include "ring.h"

#include "mem.h"
#include "assert.h"

#include <stdarg.h>

// For a ring: 01234
// 1  2  3  4  5  6  <-- positive index
// 0  1  2  3  4
//-5 -4 -3 -2 -1  0  <-- negative index

#define T Ring_T

struct T {
    struct node {
        struct node *llink, *rlink;
        void *value;
    } *head;
    int length;
};

T Ring_new()
{
    T ring;
    NEW0(ring);
    ring->head = NULL;
    return ring;
}

T Ring_ring(void *x, ...)
{
    va_list ap;
    T ring = Ring_new();
    
    va_start(ap, x);
    for (; x; x = va_arg(ap, void*))
        Ring_addhi(ring, x);
    va_end(ap);
    return ring;
}

void Ring_free(T *ring)
{
    assert(ring && *ring);

    struct node *p = (*ring)->head, *q;
    if (p != NULL) {
        int n = (*ring)->length;
        for (; n-- > 0; p = q) {
            q = p->rlink;
            FREE(p);
        }
    }
    FREE(*ring);
}

int Ring_length(T ring)
{
    assert(ring);
    return ring->length;
}

// i in [0, length-1] from low to high means [head node, tail node]
static struct node*
get_node(T ring, int i)
{
    int n;
    struct node *p = ring->head;
    if (i <= ring->length/2) {
        // Start from head
        for (n = i; n > 0; n--)
            p = p->rlink;
    } else {
        // Start from head, so need to ->llink to the tail node
        for (n = ring->length - i; n > 0; n--)
            p = p->llink;
    }
    return p;
}

static void delete_node(T ring, struct node *p)
{
    p->llink->rlink = p->rlink;
    p->rlink->llink = p->llink;
    FREE(p);
    if (--ring->length == 0)
        ring->head = NULL;
}

void* Ring_get(T ring, int i)
{
    assert(ring);
    assert(i >= 0 && i < ring->length);
    
    struct node *p = get_node(ring, i);
    return p->value;
}

void* Ring_put(T ring, int i, void *x)
{
    assert(ring);
    assert(i >= 0 && i < ring->length);
    
    struct node *p = get_node(ring, i);
    void *prev = p->value;
    p->value = x;
    return prev;
}

// Insert p to the left of q
static void
insert_to_left(T ring, struct node *p, struct node *q)
{
    if (q == (void*)-1) {
        ring->head = p;
        p->llink = p->rlink = p;
    } else {
        p->llink = q->llink;
        q->llink->rlink = p;
        p->rlink = q;
        q->llink = p;
    }
    ring->length++;
}

// Insert to pos [1, length+1] or [-length, 0]
// [1] or [-length] means add to head
// [length+1] or [0] means add to tail
void* Ring_add(T ring, int pos, void *x)
{
    assert(ring);
    assert(pos >= -ring->length && pos <= ring->length + 1);
    
    if (pos == 1 || pos == -ring->length) {
        return Ring_addlo(ring, x);

    } else if (pos == 0 || pos == ring->length + 1) {
        return Ring_addhi(ring, x);

    } else {
        int i = pos < 0 ? ring->length + pos : pos - 1;
        struct node *q = get_node(ring, i);

        struct node *p;
        NEW(p);
        p->value = x;
        insert_to_left(ring, p, q); 
        return x;
    }
}

// Add to head
void* Ring_addlo(T ring, void *x)
{
    assert(ring);
    Ring_addhi(ring, x);
    ring->head = ring->head->llink;
    return x;
}

// Add to tail
void* Ring_addhi(T ring, void *x)
{
    assert(ring);
    
    struct node *p, *q;
    NEW(p);
    if (ring->head == NULL)
        q = (void*)-1;
    else
        q = ring->head;
    p->value = x;
    insert_to_left(ring, p, q);
    return x;
}

void* Ring_remove(T ring, int i)
{
    assert(ring);
    assert(ring->length > 0);
    assert(i >= 0 && i < ring->length);

    struct node *p = get_node(ring, i);
    void *x = p->value;

    if (i == 0)
        ring->head = p->rlink;
    delete_node(ring, p);
    return x;
}

void* Ring_remlo(T ring)
{
    assert(ring);
    assert(ring->length > 0);

    ring->head = ring->head->rlink;
    return Ring_remhi(ring);
}

void* Ring_remhi(T ring)
{
    assert(ring);
    assert(ring->length > 0);

    struct node *p = ring->head->llink;
    void *x = p->value;

    delete_node(ring, p);
    return x;
}

// Locate head at n:
//   If n >= 0 then rotate to right to choose head
//   If n < 0 then rotate to left to choose head
void Ring_rotate(T ring, int n)
{
    assert(ring);
    assert(n >= -ring->length && n <= ring->length);

    int i;
    if (n >= 0)
        i = n % ring->length;
    else
        i = n + ring->length;

    struct node *p = get_node(ring, i);
    ring->head = p;
    return;
}

